\section{Análisis}


Para analizar el comportamiento de las estrategias, generamos distintos patrones de acceso a la base de datos (trazas). Corrimos las diferentes estrategias para cada traza, haciendo variar el tamaño del Pool. Para cada una de estas corridas, calculamos el hit rate de cada estrategia. Luego representamos estos resultados en gráficos comparativos que utilizamos para verificar nuestras hipotesis.

\subsection{Generación de Trazas} 

Las trazas que generamos son:

\begin{enumerate}
  \item Múltiples trazas combinadas con el mixer provisto por la cátedra. Luego se intercala un File Scan. Finalmente se repiten las trazas del comienzo. Cantidad de operaciones = Aprox. 60000 
  \item Caso similar al anterior pero en vez de intercalar un file scan, aparece un index scan. Cantidad de operaciones: Aprox. 1600
  \item File Scan de 100 páginas, seguido de otro exactamente igual. 
\end{enumerate}

Elegimos estas trazas como medidas de comparación ya que contienen casos problemáticos antes mencionados. La idea con las primeras 2 trazas es la de plantear una situación de accesos a la base de datos que se asemeje a un uso posible real. Los file scan/index scan intercalados tienen el objetivo de testear si el algoritmo de touch count provee de un "salvavidas" frente a la pérdida de la cache que provocan dichos scans. 

La tercer traza se construyo con el fin de ver el efecto de la separación de buffers en hot y cold del algoritmo de touch count frente a file scans seguidos sobre las mismas paginas. 

En todos los casos se varió el tamaño del buffer pool para comparar los hitrates obtenidos en cada estrategia. En el ultimo caso se usaron tamaños de buffer pool menores a la cantidad de páginas leidas por los filescan para demostrar
el problema de los algoritmos de fifo y lru en estos casos. 

\subsection{Resultados obtenidos} 

\subsubsection*{Primera traza}
\begin{table}[h]
\centering
\begin{tabular} {|l|l|l|l|l|}
  \hline
  Pool size & FIFO & LRU & MRU & Touch \\
  \hline
  203 & 0.4774693350 & 0.4646223369 & 0.4369270497 & 0.4978050355 \\
  250 & 0.5557133634 & 0.5768237572 & 0.5524209167 & 0.6179470626 \\
  300 & 0.6717236927 & 0.6724338282 & 0.6750806972 & 0.7101678502 \\
  350 & 0.7909296320 & 0.7606843124 & 0.7936087798 & 0.8073595868 \\
  500 & 0.9855713363 & 0.9855713363 & 0.9855713363 & 0.9855713363 \\
  \hline
\end{tabular}
\caption{Hit Rate para la primer traza en función del pool size}
\label{tab:myfirsttable}
\end{table}


En el primer gráfico se da el resultado esperado de una mejor performance del algoritmo de touchcount frente al resto. Se observa una mejora de aproximadamente un 4\% frente al \textit{LRU}, y entre un 6\% y 7\% frente a \textit{FIFO} y \textit{MRU}. Si bien las diferencias son pequeñas, se mantienen para todos los tamaños de buffer pool.

\subsubsection*{Segunda traza}

\begin{table}[h]
\centering
\begin{tabular} {|l|l|l|l|l|}
  \hline
  Pool size & FIFO & LRU & MRU & Touch \\
  \hline
10 & 0.0012033694 & 0.0012033694 & 0.0457280385 & 0.0276774969 \\
50 & 0.0240673886 & 0.0264741275 & 0.2141997593 & 0.1034897713 \\
100 & 0.3658243080 & 0.3706377858 & 0.3935018050 & 0.3092659446 \\
150 & 0.6040914560 & 0.5571600481 & 0.6305655836 & 0.6582430806 \\
250 & 0.7388688327 & 0.7388688327 & 0.7388688327 & 0.7388688327 \\
 \hline
\end{tabular}
\caption{Hit Rate para la segunda traza en función del pool size}
\label{tab:mysdfirsttable}
\end{table}


En el caso de la segunda traza, para tamaños menores de buffer pool obtenemos resultados particulares. Para 10 y 50 frames, MRU es la mejor opcion, seguida por touchcount; y para tamaño 100, touch count tiene la peor performance de las 4 estrategias.

Sin embargo, para un tamaño de 150, la estrategia de touch count pasa a tener la mayor cantidad de hits. Estos resultados se los atribuimos a la naturaleza aleatoria del generador de trazas; pero lo que nos permite ver es que
aunque el algoritmo de touch count sea un buen algoritmo en muchos casos, seguirán existiendo otros en los que estrategias más básicas lo superen en performance. 

\subsubsection*{Tercera traza}

\begin{table}[h]
\centering
\begin{tabular} {|l|l|l|l|l|}
  \hline
  Pool size & FIFO & LRU & MRU & Touch \\
  \hline
10 & 0.0 & 0.0 & 0.045 & 0.025 \\
40 & 0.0 & 0.0 & 0.2 & 0.1 \\
70 & 0.01 & 0.03 & 0.35 & 0.18 \\
100 & 0.5 & 0.5 & 0.5 & 0.5 \\
 \hline
\end{tabular}
\caption{Hit Rate para la tercer traza en función del pool size}
\label{tab:my3dfirsttable}
\end{table}


En este último caso se dan los resultados que se esperaban. Al ser filescans sobre 100 paginas, los casos con buffer pool de tamaño menor a 100 debian dar un hitrate igual a 0 para las estrategias de LRU y FIFO, pero mayor a 0 en 
MRU y TouchCount. Se observa exactamente eso. Entre las 2 últimas, MRU parece tener mejor performance. En el caso de tamaño = 70, se ve que para LRU y FIFO el hitrate no es exactamente 0. Eso lo atribuimos a detalles menores de
implementación que quizás generan buffers con la misma fecha de utilización, y no los consideramos reelevantes. 


\subsection{Conclusiones}

Con los resultados obtenidos se puede concluir que el algoritmo de touch count provee ventajas sobre los más básicos LRU, FIFO y MRU, ya que permite reducir los efectos nocivos de un file scan sobre la cache. Sin embargo, como 
comentamos previamente, siguen existiendo combinaciones de trazas que tendrían un mayor hitrate si se utilizaran estos algoritmos sencillos. Esto nos dice que quizás siga existiendo espacio para mejorar la selección de 
víctimas de un buffer pool. Una posibilidad sería el tratar de que el algoritmo identifique los casos en los que el touchcount no representa la mejor opción antes de aplicarlo.  

\begin{figure}
  \centering
    \includegraphics[]{diagramas/grafico1.png}
  \caption{Hit rates en función del algoritmo elegido y del buffer size - Primer Traza}
  \label{fig:ejemplo}
\end{figure}


\begin{figure}
  \centering
    \includegraphics[]{diagramas/grafico2.png}
  \caption{Hit rates en función del algoritmo elegido y del buffer size - Segunda Traza}
  \label{fig:ejemplo}
\end{figure}


\begin{figure}
  \centering
    \includegraphics[]{diagramas/grafico3.png}
  \caption{Hit rates en función del algoritmo elegido y del buffer size - Tercera Traza}
  \label{fig:ejemplo}
\end{figure}
